A content addressable memory (CAM), also known as an associative memory, is a data storage device in which a location is identified by its informational content rather than by the names, addresses, or relative positions, and from which the data may be retrieved. For applications requiring content addressable processing, existing solutions make use of content addressable memories having a memory plane formed by an array of CMOS static memory cells.
U.S. Pat. No. 5,452,243 to Ansel et al. discloses a fully static CAM cell with low write power (minimum power supply current surges), but it has a total of seventeen transistors in the disclosed embodiment. It would be desirable to have a smaller memory cell that uses fewer transistors. U.S. Pat. No. 5,475,633 to Mehalel discloses a four-transistor cache memory cell. However, the cell disclosed is pseudo-static and still requires refresh operations to be performed. It would be desirable to have a static memory cell that does not require refresh operations.
U.S. Pat. No. 5,386,379 to Ali-Yahia et al. discloses a static CAM cell using eight transistors. The transistors are divided into two arrays, the first array having a data storage function and the second array having a comparison function between the stored data item and a data item being applied to the input of the cell, the comparison result being obtained on a selection line. In the first embodiment, the first array comprises four transistors for storage purposes and two access transistors connected to two bit lines and a word line, the second array comprises two transistors, the two access transistors of the first array being associated with these two transistors of the second array in order to ensure the comparison function, the data item to be compared being applied to the bit lines connected to the two access transistors of the cell. The selection line is preloaded during reading-writing operations and during comparison operations. A second ten-transistor cell embodiment in the patent eliminates the need to preload the selection line; however two additional transistors need to be added to the cell.
The eight-transistor memory cell of Ali-Yahia et al. operates well in isolation. However, there is a problem that occurs when more than one memory cell is on the same selection line. Referring to FIG. 2, which shows the memory cell described in Ali-Yahia et al., the selection line 29 is always preloaded to a "1" logic state. Nodes 91 and 92 are storage cells for data written into the memory cell. When bit line 28 is loaded to "1" and bit line 27 is loaded with a "0", there is a match and current flows from ground to Vdd through transistors 31 and 32, and node 91 of the cell will be pulled towards ground. However, if bit line 28 is loaded with a "0" and bit line 27 is loaded with a "1", there is not a match, and current flows from Vdd to ground through transistors 34 and 33 and node 92 is pulled towards Vdd. Therefore, if a matching cell and a non-matching cell are on the same selection line 29, there will be a mismatch on the selection line as the matching cell will be pulled towards ground and the non-matching cell will be pulled towards Vdd. This could cause the state of one of the cells to change to the opposite state, thus compromising the stability of the memory cell. This problem can be obviated by making node 91 large, such that it can source a greater amount of current than the current that flows through transistors 34, 33 and 37 to ground. Thus, it would be necessary to make the saturated drain current at node 91 much larger than the saturated drain current of transistor 36. However, it would be desirable not to have to be concerned with having to increase the size of node 91 to avoid compromising the stability of the memory cell.
Another problem that could occur would be in the case where there are more than two memory cells--for example N cells, where N is typically 24-32 bits wide. Then, if all but one cell match, then there will be (N-1) cells having transistors of the size of node 91 pulling the selection line 29 up and only one cell having one transistor 31 or 33 pulling the match line 29 through transistors 36 or 37. Since there is only one cell driving the line low and (N-1) cells driving the line high, the voltage on the selection line 29 will stay high and the mismatch will not be detected.
Additionally, even if the circuit of Ali-Yahia et al. could be made to work with multiple cells, it is not a low power solution. In the first embodiment of Ali-Yahia et al., it is necessary to precharge the selection line 29 in order to avoid the transistors of the comparison logic 36 and 37 forming an unloading path from the match line into the storage cells 91 and 92, which could also compromise the stability of the memory cell. In CAMs, only one line matches at a time, so if there are M words in the memory, then every (M-1) signals will have to be precharged and discharged for every cycle. This precharging and discharging consumes power equal to (C.times.Vdd.sup.2 .times.F), where C is the capacitance of the signal and F is the operating frequency. It would be desirable not to have to precharge the match line.
In a multiprocessor system, there is a need to keep the caches coherent, as the introduction of caches can cause a coherence problem for multiprocessors if the view of memory through the cache of one processor is different from the view of memory obtained through the cache of another processor. To keep the caches coherent involves two entities, the processor and the bus, looking at the look up mechanism simultaneously. However, using common methods known in the art, such as dual look up mechanisms or inclusion methods, problems occur when updating one of the look up mechanisms by one entity while the other is accessing the look up mechanism. To eliminate these problems, it would be desirable to provide a content addressable memory with more than one access port to allow two simultaneous read operations or to allow simultaneous read and write operations.
It is an object of the present invention to provide a static content addressable memory that is fast, uses a minimal amount of transistors and operates when multiple memory cells are provided in a manner that does not compromise the stability of the memory cells.
It is a further object of the invention to provide a static CAM that does not require precharging, and thus requires less power.
It is another object of the invention to provide a dual port cam which allows two simultaneous read operations or simultaneous read and write operations in order to keep the memory caches coherent.